// https://leetcode.cn/problems/valid-sudoku/
// Created by ade on 2022/8/18.
//
#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

class Solution {
public:
    // 最笨的方法
    bool isValidSudoku1(vector <vector<char>> &board) {
        for (int i = 0; i < 9; i++) {
            int m[9] = {0};
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                m[board[i][j] - '1']++;
                if (m[board[i][j] - '1'] > 1) return false;
            }

            int n[9] = {0};
            for (int j = 0; j < 9; j++) {
                if (board[j][i] == '.') continue;
                n[board[j][i] - '1']++;
                if (n[board[j][i] - '1'] > 1) return false;
            }
        }
        vector <vector<int>> starts = {
                {0, 0},
                {0, 3},
                {0, 6},
                {3, 0},
                {3, 3},
                {3, 6},
                {6, 0},
                {6, 3},
                {6, 6},
        };
        for (auto start : starts) {
            int m[9] = {0};
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (board[start[0] + i][start[1] + j] == '.') continue;
                    m[board[start[0] + i][start[1] + j] - '1']++;
                    if (m[board[start[0] + i][start[1] + j] - '1'] > 1) return false;
                }
            }
        }
        return true;
    }

    bool isValidSudoku(vector <vector<char>> &board) {
        int r[9][9];
        int c[9][9];
        int g[3][3][9];
        memset(r, 0, sizeof(r));
        memset(c, 0, sizeof(c));
        memset(g, 0, sizeof(g));
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char m = board[i][j];
                if (m == '.') continue;
                r[i][m - '1']++;
                c[j][m - '1']++;
                int num = (i - 1) * 9 + j;
                g[i / 3][j / 3][m - '1']++;
                if (r[i][m - '1'] > 1 || c[j][m - '1'] > 1 || g[i / 3][j / 3][m - '1'] > 1) {
                    return false;
                }
            }
        }
        return true;
    }
};

int main() {
    Solution so;
    vector <vector<char >> board = {{'.', '.', '4', '.', '.', '.', '6', '3', '.'},
                                    {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                                    {'5', '.', '.', '.', '.', '.', '.', '9', '.'},

                                    {'.', '.', '.', '5', '6', '.', '.', '.', '.'},
                                    {'4', '.', '3', '.', '.', '.', '.', '.', '1'},
                                    {'.', '.', '.', '7', '.', '.', '.', '.', '.'},

                                    {'.', '.', '.', '5', '.', '.', '.', '.', '.'},
                                    {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                                    {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};
    cout << so.isValidSudoku(board) << endl;
    return 0;
}